// ml:run = $bin < input
#include <iostream>
#include <vector>

long long constexpr mod = 1000000007;

struct matrix
{
	using value_type = long long;
	using row_type = std::vector<value_type>;

	matrix(int ro, int co)
	{
		mat.resize(ro);
		for (auto & i : mat) i.resize(co);
	}

	matrix(int n) : matrix(n, n)
	{
		for (int i = 0; i < n; i++) mat[i][i] = 1;
	}

	matrix() = default;

	int row() const { return mat.size(); }
	int col() const { return mat[0].size(); }

	row_type       & operator[](int x)       { return mat[x]; }
	row_type const & operator[](int x) const { return mat[x]; }

	private:
	std::vector<row_type> mat;
};

matrix operator*(matrix const & a, matrix const & b)
{
	int n = a.row(), m = b.col(), t = a.col();
	matrix r(n, m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < t; k++)
				r[i][j] = (r[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
	return r;
}

matrix quick_pow(matrix const & a, long long b)
{
	if (!b) return matrix(a.row());

	matrix ret = quick_pow(a, b / 2);
	ret = ret * ret;
	if (b & 1) ret = ret * a;
	return ret;
}

using ll = long long;
ll const mo = 1000000007;
ll n, m, k;

ll quick(ll a, ll b)
{
    ll ret = 1;
    for (; b; a = (a * a) % mo, b /= 2)
        if (b & 1) ret = (ret * a) % mo;
    return ret;
}

ll calc(ll n, ll m)
{
    if (m == 0) return quick(k * (k - 1), n);
	matrix a(m + 3, m + 3);
    for (int i = 0; i < m; i++)
        a[0][i] = (quick(k, i) * (k - 1) * k) % mo;
    a[0][m + 2]= (quick(k, m) * k * (k - 1)) % mo;
    /* a[0][m + 1] = (quick(k, m) * k * (k + 1) * 2ll) % mo; */
    for (int i = 1; i <= m + 1; i++)
        a[i][i - 1] = 1;
    a[m + 2][m + 2] = k * k;

    matrix init(m + 3, 1);
    for (int i = 0; i < m; i++)
        init[m + 1 - i][0] = 0;
    init[1][0] = quick(k, m);
    init[0][0] = ((k - 1) * k * quick(k, m) * 2ll) % mo;
    init[m + 2][0] = k * k;

    if (n <= m + 1) return init[m + 1 - n][0];
    a = quick_pow(a, n - m - 1);
    init = a * init;
    return init[0][0];
}

int main()
{
	std::ios::sync_with_stdio(false);
    int T; std::cin >> T;
    while (T--) {
        std::cin >> n >> m >> k;
        ll ans = calc(n, m);
        ans = (ans + mo) % mo;
        std::cout << ans << "\n";
    }
}

